package com.zhanghp.class036;

import com.zhanghp.common.TreeNode;

/**
 * 二叉树的最大特殊宽度<br/>
 * 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/
 *
 * @author zhanghp
 * @since 2024/4/17 17:47
 */
public class Code03_WidthOfBinaryTree {

    static class Solution {

        public int MAX_SIZE = 3_001;

        /**
         * 记录树节点，用于处理每层树节点的业务
         */
        public TreeNode[] nq = new TreeNode[MAX_SIZE];

        /**
         * 记各个节点所在的位置，用来记算最大宽度
         */
        public int[] iq = new int[MAX_SIZE];

        public int l, r;

        public int widthOfBinaryTree(TreeNode root) {
            int ans = 1;
            l = r = 0;
            // 节点初始化
            nq[r] = root;
            // 计数初始化
            iq[r++] = 1;
            while (l < r) {
                // 获取每层有多少个节点
                int size = r - l;
                ans = Math.max(ans, iq[r - 1] - iq[l] + 1);
                // 循环该层，便利该层所有节点是否有子节点
                for (int i = 0; i < size; i++) {
                    TreeNode node = nq[l];
                    // 获取节点的id，便于处理
                    int id = iq[l ++];
                    if (node.left != null) {
                        nq[r] = node.left;
                        iq[r ++] = id * 2;
                    }
                    if (node.right != null) {
                        nq[r] = node.right;
                        iq[r ++] = id * 2 + 1;
                    }
                }
            }
            return ans;
        }
    }
}
